#ifndef USER_ALGOR_H_
#define USER_ALGOR_H_

#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <cstring>
#include "heap_sort.h"

using namespace std;

template<typename Type>
inline void swap(Type *ix, Type *iy)
{
	Type temp;
	
	temp = *ix;
	*ix = *iy;
    *iy = temp;	
}

/* Insert sort */
template <typename Type>
inline void insertSort(vector<Type> &nums)
{
	for (int ix = 1; ix < nums.size(); ix++) {
		Type temp = nums[ix];
		int jy;
		for ( jy = ix - 1; jy >= 0 && nums[jy] > temp; jy --)
			nums[jy + 1] = nums[jy];
		
		nums[jy + 1] = temp;
	}
}

template <typename Type>
inline void insertSort(Type *a, int n)
{
    for (int ix = 1; ix < n; ix ++)	{
		Type temp = a[ix];
		int jy;
		for (jy = ix - 1; jy >= 0 && a[jy] > temp; jy--)
			a[jy + 1] = a[jy];
		
		a[jy + 1] = temp;
	}
}

/* Bubble Sort */
template <typename Type>
inline void bubbleSort(Type *a, int n)
{
	for (int ix = 0; ix < n-1; ix ++) {
		for (int jy = n-1; jy > ix; jy --) {
			if (a[jy] < a[ix])
				swap(&a[ix], &a[jy]);
		}
	}
}


/* quick sort */
template<typename Type>
inline int partition(Type *a, int left, int right)
{
	int ix = left;
	int jy = right;
	
	while (ix < jy) {
		while (a[jy] > a[ix])
			jy --;
		if (ix < jy)
		    swap(a[jy], a[ix]);
			
		while (a[ix] < a[jy])
			ix ++;
		if (ix < jy)
		    swap(a[ix], a[jy]);
	}
	return ix;
}

template <typename Type>
inline void quickSort(Type *a, int left, int right)
{
	if (right <= left)
		return;
	
	Type privot = partition(a, left, right);
	quickSort(a, left, privot - 1);
	quickSort(a, privot + 1, right);
}

/* select Sort */
template<typename Type>
void selectSort(Type *a, int n)
{
	for (int ix = 0; ix < n - 1; ix ++) {
		int smallest = ix;
		for (int jy = ix + 1; jy < n; jy ++)
			if (a[smallest] > a[jy])
				smallest = jy;
		swap(a[ix], a[smallest]);
	}
}

/* Heap sort */
template <typename Type>
void heap(Type *a, int first, int end)
{
	int father = first;
	int son = father * 2 + 1;
	
	while (son < end) {
		if (son + 1 < end && a[son] < a[son + 1])
			son ++;
		if (a[father] > a[son]) 
			break;
		else {
			swap(a[father], a[son]);
			father = son;
			son = 2 * father + 1;
		}
	}
}

template <typename Type>
inline void heapSort(Type *a, int n)
{
	int ix;
	// init heap
	for (ix = n/2; ix >= 0; -- ix) {
		heap(a, ix, n);
	}
	
	for (ix = n - 1; ix > 0; -- ix) {
		swap(a[0], a[ix]);
		heap(a, 0, ix);
	}
}

template <class Type>
inline void heap_sort(Type *a, int n)
{
	MaxHeap<Type> heap(a, n);
	
	heap.removeMax();
}

/* shell Sort */
template <typename Type>
void shellSort(Type *a, int n)
{
	for (int delta = n/2; delta > 0; delta /= 2) {
		for (int ix = 0; ix < delta; ix ++) {
			for (int jy = ix + delta; jy < n; jy += delta) {
				for (int k = jy; k > 0; k -= delta) {
					if (a[k] < a[k - 1])
                        swap(a[k - 1], a[k]);	
				}
								 
			}
		}
	}
}

/* merge sort */
template<typename Type>
void merge(Type *a, Type *temp, int left, int right, int mid)
{
	int index1 = left;
	int index2 = mid + 1;
	int ix;
	for (ix = left; (index1 <= mid)&&(index2 <= right); ix++) {
		if (a[index1] < a[index2])
			temp[ix] = a[index1++];
		else
			temp[ix] = a[index2++];
	}
	
	while (index1 <= mid)
		temp[ix++] = a[index1++];
	
	while (index2 <= right)
		temp[ix++] = a[index2++];
	for (ix = left; ix <= right; ix++)
		a[ix] = temp[ix];
}


template <typename Type>
void mergeSort(Type *a, Type *temp, int left, int right)
{
	if (left < right) {
		int middle = (left + right)/2;
		mergeSort(a, temp, left, middle);
		mergeSort(a, temp, middle + 1, right);
		merge(a, temp, left, right, middle);
	}
}


/* radix sort */
template <typename Type>
Type keySize(Type *a, int size)
{
	int key_size = 1;
	for (int ix = 0; ix < size; ix ++) {
		int temp = 1;
		int n = 10;
		while(a[ix]/n > 0) {
			temp ++;
			n *= 10;
		}
		key_size = temp;
	}
	return key_size;
}

template <typename Type>
void radixSort(Type *a, int size)
{
	Type temp[10][size] = {0};
	int order[10] = {0};
	int ix;
	int key_size = keySize(a, size);
	
	for (int n = 1; key_size > 0; n *= 10, key_size --) {
		for (ix = 0; ix < size; ix ++) {
			int lsd = (a[ix]/n) %10;
			temp[lsd][order[lsd]] = a[ix];
			order[lsd] ++;
		}
		int k = 0;
		for (ix = 0; ix < 10; ix ++) {
			if (order[ix] != 0) {
				for (int jy = 0; jy < order[ix]; jy ++) {
					a[k] = temp[ix][jy];
					k++;
				}
				order[ix] = 0;
			}
		}
	}
}


template <typename Type>
inline void bucketSort(Type *a, int n)
{
	Type *buckets;
	int ix, jy;
	Type max = a[0];
	
	if(a == NULL || n < 1 || max < 1)
		return;
	
	for (ix = 0; ix < n; ix ++){
		if(max < a[ix])
		    max = a[ix];
	}
		
	if ((buckets = new Type[max]) == NULL)
		return;
	memset(buckets, 0, max*sizeof(Type));
	
	for (ix = 0; ix < n; ix ++)
		buckets[a[ix]]++;
	
	for (ix = 0, jy = 0; ix < max; ix++) {
		while ((buckets[ix]--) > 0)
			a[jy++] = ix;
	}
	
	delete [] buckets;
}


/* Matrix calculate */
template <typename Type>
inline void matrixMultiplyLow(Type **a, Type **b, Type **c, int n)
{
	for (int i = 0; i < n; i ++) {
		for (int j = 0; j < n; j ++) {
			Type sum = 0;
			for (int k = 0; k < n; k ++) {
				sum += a[i][k] * b[k][j];
			}
			c[i][j] = sum;
		}
	}
}


template <typename Type>
inline void matrixMultiplyHigh(Type **a, Type **b, Type **c, int n)
{
	for (int i = 0; i < n; i ++) {
		for (int k = 0; k < n; k ++) {
			for (int j = 0; j < n; j ++) {
				c[i][j] += a[i][k] * b[k][j];			
		    }
		}		
	}
}


template <typename Type>
inline void matrixMultiplyHigh(Type **a, Type **b, Type **c, int m, int n, int p)
{
	for (int i = 0; i < m; i ++) {
		for (int k = 0; k < n; k ++) {
			for (int j = 0; j < p; j ++) {
				c[i][j] += a[i][k] * b[k][j];			
		    }
		}		
	}
}

#endif